/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_LIST_H_VERSION_SSTD__
#define __STD_LIST_H_VERSION_SSTD__

#define _SSTD_USE_LIST_
#define _USE_LIST_BACKUP_BUF

#include "memory.hpp"
#include "functional.hpp"
SSTL_BEGIN
#ifdef _SSTD_USE_LIST_
// CLASS list {
template<typename Type, class Allocate = allocator<Type>>
class list 
{
	// TYPE {
public:
	SSTD_NEST_TYPE_DEFINE(Type);
protected:
	struct _node_base_;
	struct _node_data_;
	class _iterator_;
	typedef _node_base_ _node_type;
	typedef typename _node_base_ * _node_pointer;
	typedef _memory_helper_<value_type> _helper;
	typedef typename Allocate::rebind<_node_base_>::other node_allocator_type;
public:
	STD_ITERATOR_DEFINE(_iterator_);
	typedef typename Allocate::rebind<_node_data_>::other allocator_type;
	// TYPE }
protected:
	typedef allocator_type _allocator;
	typedef node_allocator_type _node_allocator;
	// DATA {
	static const size_type _MIN_BACKUP_SIZE = 16;
	mutable _node_pointer _buckup_list;
	mutable size_type _backup_size;
	_node_pointer _tail;
	size_type _size;
	// DATA }
public:
	// CONSTRUCTOR {
	list()
		: _size(0)
		, _backup_size(0)
		, _buckup_list(0)
	{
		this->_init_tail();
	}
	list(list const &o)
		: _size(0)
		, _backup_size(0)
		, _buckup_list(0)
	{
		this->_init_tail();
		if(o._size == 0) return;
		this->_insert_i(_tail, o._size, o.begin());
		if(o._backup_size == 0) return;
		SSTD::swap(_buckup_list, o._buckup_list);
		SSTD::swap(_backup_size, o._backup_size);
	}
	list(size_type num, const_reference value)
		: _size(0)
		, _backup_size(0)
		, _buckup_list(0)
	{
		this->_init_tail();
		if(num == 0) return;
		this->_insert(_tail, num, value);
	}
	template<typename InIter>
	list(InIter first, InIter last)
		: _size(0)
		, _backup_size(0)
		, _buckup_list(0)
	{
		this->_init_tail();
		size_type num = SSTD::distance(first, last);
		this->_insert_i(_tail, num, first);
	}
	~list()
	{
		ASSERT_REPAIR(_tail, return);
		this->_erase(_size, _tail->next, _tail->prev);
		_tidy_tail();
		_tidy();
	}
	// CONSTRUCTOR }
	// OTHER {
	void swap(list &o)
	{
		SSTD::swap(this->_tail, o._tail);
		SSTD::swap(this->_size, o._size);
	}	
	void clear()
	{
		this->_erase(_size, _tail->next, _tail->prev);
	}
#ifdef _USE_SSTD_EXTRA
	void tidy()
	{
		this->_tidy();
	}
#endif // _USE_SSTD_EXTRA
	void reverse()
	{
		if(_size <= 1) return;
		_node_pointer node = _tail;
		do
		{
			_reverse_link(node->prev, node, node->next);
			node = node->prev;
		}
		while(node != _tail);
	}
	void resize(size_type size, const_reference value)
	{
		if(size < _size)
		{
			_node_pointer node = this->_backward(_tail, _size - size);
			_erase(_size - size, node, _tail->prev);
		}
		else if(size > _size)
		{
			this->_insert(_tail, size - _size, value);
		}
	}
	// OTHER }
	// ASSIGN {
	list & operator = (list const &o)
	{
		if(&o == this) return *this;
		this->_erase(_size, _tail->next, _tail->prev);
		this->_insert_i(_tail, o._size, o.begin());
		return *this;
	}
	void assign(size_type num, value_type const value)
	{
		this->_erase(_size, _tail->next, _tail->prev);
		this->_insert(_tail, num, value);
	}
	template<typename InIter>
	void assign(InIter first, InIter last)
	{	// dont assign self.
		size_type num = distance(first, last);
		this->_erase(_size, _tail->next, _tail->prev);
		this->_insert_i(_tail, num, first);
	}
	// ASSIGN }
	// ERASE & INSERT {
	iterator erase(_iterator_ pos)
	{
		ASSERT_REPAIR(_valid_data(pos), return end());
		_node_pointer next = pos._node->next;
		this->_erase(pos._node);
		return iterator(next);
	}
	iterator erase(_iterator_ from, _iterator_ to)
	{		
		ASSERT_REPAIR(_valid_data(from) && _valid_iterator(to), return end());
		size_type num = SSTD::distance(from, to);
		ASSERT_REPAIR(_size >= num, return end());
		this->_erase(num, from._node, (--to)._node);
		return iterator(to);
	}
	void remove(const_reference value)
	{
		remove_if(SSTD::bind1st(SSTD::equal_to<value_type>(), value));
	}
	template<typename Bool>
	void remove_if(Bool fun)
	{
		_node_pointer node = _tail->next;
		while(node != _tail)
		{
			node = node->next;
			if(fun(_visit(node->prev)))
			{
				this->_erase(node->prev);
			}
		}
	}
	iterator insert(_iterator_ pos, const_reference value)
	{
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		this->_insert(pos._node, value);
		return iterator(pos._node->prev);
	}
	iterator insert(_iterator_ pos, size_type num, const_reference value)
	{
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		_node_pointer prev = pos._node->prev;
		this->_insert(pos._node, num, value);
		return iterator(prev->next);
	}
	template<typename InIter>
	iterator insert(_iterator_ pos, InIter first, InIter last)
	{
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		_node_pointer prev = pos._node->prev;
		size_type num = SSTD::distance(first, last);
		this->_insert_i(pos._node, num, first);
		return iterator(prev->next);
	}
	// ERASE & INSERT }
	// PUSH & POP {
	void push_back(const_reference value)
	{
		this->_insert(_tail, value);
	}
	void push_front(const_reference value)
	{
		this->_insert(_tail->next, value);
	}
	void pop_back()
	{
		ASSERT_REPAIR(_size, return);
		_erase(_tail->prev);
	}
	void pop_front()
	{
		ASSERT_REPAIR(_size, return);
		_erase(_tail->next);
	}
	// PUSH & POP }
	// FRONT BACK {
	reference front()
	{
		return _visit(_tail->next);
	}
	reference back()
	{
		return _visit(_tail->prev);
	}
	const_reference front() const
	{
		return _visit(_tail->next);
	}
	const_reference back() const
	{
		return _visit(_tail->prev);
	}
	// FRONT BACK }
	// VISIT ITERATOR {
	iterator begin()
	{
		return iterator(this->_make_iterator(_tail->next));
	}
	iterator end()
	{
		return iterator(this->_make_iterator(_tail));
	}
	const_iterator begin() const
	{
		return iterator(this->_make_iterator(_tail->next));
	}
	const_iterator end() const
	{
		return iterator(this->_make_iterator(_tail));
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(this->_make_iterator(_tail->prev));
	}
	reverse_iterator rend()
	{
		return reverse_iterator(this->_make_iterator(_tail));
	}
	const_reverse_iterator rbegin() const
	{
		return reverse_iterator(this->_make_iterator(_tail->next));
	}
	const_reverse_iterator rend() const
	{
		return reverse_iterator(this->_make_iterator(_tail));
	}
	// VISIT ITERATOR }
	// VISIT OTHER {
	bool empty() const
	{
		return _size == 0;
	}
	size_type size() const
	{
		return _size;
	}
	allocator_type get_allocator() const
	{
		return _allocator();
	}
	size_type max_size() const
	{
		return _allocator::max_size();
	}
	// VISIT OTHER }
	// ALGORITHM {
	void splice(_iterator_ pos, list &src)
	{
		if(&src == this) return;
		if(src._size == 0) return;
		_node_pointer front = src._tail->next, back = src._tail->prev;
		size_type num = src._size;
		src._unjoin(num, front, back);
		this->_join(pos._node, num, front, back);
	}
	void splice(_iterator_ pos, list &src, _iterator_ src_pos)
	{
		if(&src == this) return;
		src._unjoin(src_pos._node);
		this->_join(pos._node, src_pos._node);
	}
	void splice(_iterator_ pos, list &src, 
		_iterator_ src_first, _iterator_ src_last)
	{
		if(&src == this) return;
		size_type num = SSTD::distance(src_first, src_last);
		if(num == 0) return;
		--src_last;
		src._unjoin(num, src_first._node, src_last._node);
		this->_join(pos._node, num, src_first._node, src_last._node);
	}
	void unique()
	{
		this->unique(SSTD::equal_to<value_type>());
	}
	template<typename Equal>
	void unique(Equal fun)
	{
		_node_pointer node = _tail->next;
		while(node != _tail)
		{
			_node_pointer next = node->next;
			size_type count = 0;
			while(next != _tail)
			{
				if(fun(_visit(node), _visit(next)))
				{
					next = next->next;
					++count;
				}
				else break;
			}
			if(count)
			{
				this->_erase(count, node->next, next->prev);
			}
			node = next;
		}
	}
	void merge(list &src)
	{
		this->merge(src, SSTD::less_equal<value_type>());
	}
	template<typename Less>
	void merge(list &src, Less fun)
	{
		if(&src == this) return;
		_node_pointer my = _tail->next;
		_node_pointer next = src._tail->next;
		size_type count = 0;
		while(my != _tail && next !=src. _tail)
		{
			count = 0;
			while(next != src._tail)
			{
				if(fun(_visit(my), _visit(next))) break;
				next = next->next;
				++count;
			}
			if(count)
			{
				_node_pointer front = src._tail->next;
				_node_pointer back = next->prev;
				src._unjoin(count, front, back);
				this->_join(my, count, front, back);
			}
			my = my->next;
		}
		if(src._size)
		{
			_node_pointer front = src._tail->next;
			_node_pointer back = src._tail->prev;
			count = src._size;
			src._unjoin(count, front, back);
			this->_join(_tail, count, front, back);
		}
	}
	void sort()
	{
		this->sort(SSTD::less<value_type>());
	}
	template<typename Less>
	void sort(Less fun)
	{
		if(_size <= 1) return;
		size_type size = _size;
		static const int BIN_SIZE = 24;
		list carry, bin[BIN_SIZE];
		while(_size)
		{
			carry.splice(carry.begin(), *this, begin());
			int i = 0;
			while(i < BIN_SIZE && bin[i]._size)
			{
				carry.merge(bin[i], fun);
				++i;
			}
			if(i == BIN_SIZE) carry.swap(bin[BIN_SIZE - 1]);
			else carry.swap(bin[i]);
		}
		for(int i = 0; carry._size < size; ++i)
		{
			if(bin[i]._size)
			{
				carry.merge(bin[i], fun);
			}
		}
		this->swap(carry);
		return;
	}
	// ALGORITHM }
protected:
	// PROTECTED {
	// OPERATION {
	void _join(_node_pointer pos, _node_pointer in)
	{
		_link(pos->prev, in);
		_link(in, pos);
		++_size;
	}
	void _unjoin(_node_pointer out)
	{
		_link(out->prev, out->next);
		--_size;
	}
	void _join(_node_pointer pos, size_type num, _node_pointer front, _node_pointer back)
	{
		_link(pos->prev, front);
		_link(back, pos);
		_size += num;
	}
	void _unjoin(size_type num, _node_pointer front, _node_pointer back)
	{
		_link(front->prev, back->next);
		_size -= num;
	}
	void _assign(_node_pointer pos, const_reference value)
	{
		_helper::raw_fill(&_visit(pos), value);
	}
	void _assign(_iterator_ pos, size_type num, const_reference value)
	{
		_helper::raw_fill_n(pos, num, value);
	}
	void _destroy(_node_pointer pos)
	{
		_helper::destroy(&_visit(pos));
	}
	void _destroy(_iterator_ pos, size_type num)
	{
		_helper::destroy_n(pos, num);
	}	
	template<typename InIter>
	void _assign_i(_iterator_ pos, size_type num, InIter &first)
	{
		_helper::raw_copy_n(first, num, pos);
	}
	// OPERATION }
	// INSERT & ERASE {
	void _insert(_node_pointer pos, const_reference data)
	{
		_node_pointer node;
		this->_allocate(node);
		this->_assign(node, data);
		this->_join(pos, node);
	}
	void _insert(_node_pointer pos, size_type num, const_reference data)
	{
		if(num == 0) return;
		_node_pointer front, back;
		this->_allocate(num, front, back);
		this->_assign(front, num, data);
		this->_join(pos, num, front, back);
	}
	void _erase(_node_pointer in)
	{
		this->_destroy(in);
		this->_unjoin(in);
		this->_deallocate(in);
	}
	void _erase(size_type num, _node_pointer front, _node_pointer back)
	{
		if(num == 0) return;
		this->_destroy(front, num);
		this->_unjoin(num, front, back);
		this->_deallocate(num, front, back);
	}
	template<typename InIter>
	void _insert_i(_node_pointer pos, size_type num, InIter data)
	{
		if(num == 0) return;
		_node_pointer front, back;
		this->_allocate(num, front, back);
		this->_assign_i(front, num, data);
		this->_join(pos, num, front, back);
	}
	// INSERT & ERASE }
	// ALLOCATE {
	bool _backup_full() const
	{
		return _backup_size > _MIN_BACKUP_SIZE && _backup_size >= (_size >> 1);
	}
	void _init_tail()
	{
		_tail = _node_allocator::allocate(1);
		_link(_tail, _tail);
	}
	void _tidy_tail()
	{
		_node_allocator::deallocate(_tail, 1);
		_tail = 0;
	}
	void _allocate_node_data(_node_pointer &out)
	{
		out = _allocator::allocate(1);
	}
	void _deallocate_node_data(_node_pointer &in)
	{
		_allocator::deallocate(static_cast<_node_data_*>(in), 1);
	}
	void _allocate(_node_pointer &out)
	{
		if(_backup_size)
		{
			--_backup_size;
			out = _buckup_list;
			_buckup_list = _buckup_list->next;
		}
		else
		{
			_allocate_node_data(out);
		}
	}
	void _deallocate(_node_pointer in)
	{
		if(!_backup_full())
		{
			++_backup_size;
			_safe_link(in, _buckup_list);
			_buckup_list = in;
		}
		else
		{
			_deallocate_node_data(in);
		}
	}
	void _allocate(size_type num, _node_pointer &front, _node_pointer &back)
	{
		if(num == 0) return;
		if(_backup_size >= num)
		{
			_backup_size -= num;
			front = _buckup_list;
			back = _forward(_buckup_list, num - 1);
			_buckup_list = back->next;
			return;
		}		
		if(_backup_size)
		{
			front = _buckup_list;
			back = _forward(_buckup_list, _backup_size - 1);
			num -= _backup_size;
			_buckup_list = 0;
			_backup_size = 0;
		}
		else
		{
			_allocate_node_data(front);
			back = front;
			--num;
		}
		_node_pointer node;
		while(num--)
		{
			_allocate_node_data(node);
			_link(back, node);
			back = node;
		}
	}
	void _deallocate(size_type num, _node_pointer front, _node_pointer back)
	{
		if(!_backup_full())
		{
			_backup_size += num;
			_safe_link(back, _buckup_list);
			_buckup_list = front;
		}
		else
		{
			while(--num)
			{
				front = front->next;
				_deallocate_node_data(front->prev);
			}
			_deallocate_node_data(front);
		}
	}
	void _tidy()
	{
		if(_backup_size == 0) return;
		while(--_backup_size)
		{
			_buckup_list = _buckup_list->next;
			_deallocate_node_data(_buckup_list->prev);
		}
		_deallocate_node_data(_buckup_list);
		_buckup_list = 0;
	}
	// ALLOCATE }
	//  FAST FUNCTION {
	_iterator_ _make_iterator(_node_pointer node) const
	{
		return _iterator_(node, (list*)this);
	}
	bool _valid_iterator(_iterator_ const &iter) const
	{
		return iter._container == this;
	}
	bool _valid_data(_iterator_ const &iter) const
	{
		return iter._container == this && iter._node != _tail;
	}
	void _link(_node_pointer prev, _node_pointer next)
	{
		prev->next = next;
		next->prev = prev;
	}
	void _safe_link(_node_pointer prev, _node_pointer next)
	{
		if(prev) prev->next = next;
		if(next) next->prev = prev;
	}
	void _reverse_link(_node_pointer prev, _node_pointer node, _node_pointer next)
	{
		node->prev = next;
		node->next = prev;
	}
	_node_pointer _forward(_node_pointer in, size_type num)
	{
		while(num--) in = in->next;
		return in;
	}
	_node_pointer _backward(_node_pointer in, size_type num)
	{
		while(num--) in = in->prev;
		return in;
	}
	static value_type &_visit(_node_pointer node) 
	{
		return static_cast<_node_data_*>(node)->data;
	}
	//  FAST FUNCTION }
	// INNER CLASS {
	struct _node_base_
	{
		_node_base_ * prev;
		_node_base_ * next;
	};
	struct _node_data_ : public _node_base_
	{
		value_type data;
	};
	class _iterator_ 
		: public SSTD::iterator<SSTD::bidirectional_iterator_tag, value_type>
	{
		friend class list;
	private:
		_node_pointer _node;
		list* _container;
		_iterator_(_node_pointer node, list *came = 0) 
			: _node(node), _container(came)
		{}
	public:
		_iterator_() 
			: _node(0), _container(0)
		{}
		_iterator_(_iterator_ const &o) 
			: _node(o._node), _container(o._container)
		{}
		_iterator_ &operator = (_iterator_ const &o) 
		{
			_node = o._node;
			_container = o._container;
			return *this;
		}
		_iterator_ &operator ++()
		{
			_node = _node->next;
			return *this;
		}
		_iterator_ &operator --()
		{
			_node = _node->prev;
			return *this;
		}
		_iterator_ operator ++(int)
		{
			iterator temp = *this;
			_node = _node->next;
			return temp;
		}
		_iterator_ operator --(int)
		{
			iterator temp = *this;
			_node = _node->prev;
			return temp;
		}
		reference operator *()
		{
			return _visit(_node);
		}
		pointer operator ->()
		{
			return &(_visit(_node));
		}		
		const_reference operator *() const
		{
			return _visit(_node);
		}
		const_pointer operator ->() const
		{
			return &(_visit(_node));
		}
		bool operator ==(_iterator_ const &o) const
		{
			ASSERT_REPAIR(o._container == _container, return true);
			return _node == o._node;
		}
	};
	// INNER CLASS }
	// PROTECTED }
};
// CLASS list }
// FUNCTION swap (for list) {
template<typename Type, typename Allocate>
inline void swap(list<Type, Allocate> &left, list<Type, Allocate> &right)
{
	left.swap(right);
}
// FUNCTION swap (for list) }
#endif // _SSTD_USE_LIST_
SSTL_END

#ifdef _USE_LIST_BACKUP_BUF
#undef _USE_LIST_BACKUP_BUF
#endif 
#endif // __STD_LIST_H_VERSION_SSTD__
